package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/7/6 20:11
 */
public class No11_盛最多水的容器 {
    public static void main(String[] args) {
        int[] height = new int[]{7, 3, 9, 12, 18, 19, 21, 14, 8};
        Solution11 solution11 = new Solution11();
        int res = solution11.maxArea(height);
        System.out.println(res);
    }
}

class Solution11 {
    public int maxArea(int[] height) {
        //使用dp伪动态规划处理
        //定义dp[i]为底部宽为i的时候对应的最短竹竿的高度
        
        //定义dp[i]
        int[] dp = new int[height.length];
        //获取红绿指针
        int red = 0;
        int green = height.length - 1;
        int rongji = -395794;
        //迭代获取dp[i]
        for (int i = height.length - 1; i >= 1; i--) {
            //dp[i]获取
            if (height[red] <= height[green]) {
                dp[i] = height[red];
                //迭代
                red++;
            } else {
                dp[i] = height[green];
                green--;
            } 
            //每次迭代完成,计算最大容积
            rongji = Math.max(dp[i] * i, rongji);
        }
        return rongji;
    }
}



    //public int maxArea(int[] height) {
    //    //找规律:规律1:a,b组合容积为F,其中b短
    //    //则:a,b之间比b短的竹竿,直接跳过,容积均小于F
    //    
    //    //规律2:a,b组合容积F,其中b长,则移动b到a之间任何一个位置
    //    // a,b' 组合容积<F
    //    
    //    //思路:a,b判断哪个长,固定短的,同时计算容积,并移动短,逐步逼近
    //    //最后得出结果
    //    
    //    //获取长度
    //    int length = height.length;
    //    //获取红绿指针
    //    int red = 0;
    //    int green = length - 1;
    //    
    //    //最终容积
    //    int rongji = 0;
    //    //遍历每一个边,红绿指针碰到,则每一个边都遍历到
    //    out:while (red < green) {
    //        //记录红指针指向竹竿长度为a
    //        //记录绿指针指向竹竿长度为b
    //        int a = height[red];
    //        int b = height[green];
    //        //计算当前红绿指针指向的组合容积
    //        //计算距离
    //        int juli = green - red;
    //        //计算高(短的竹竿高度)
    //        int gao = Math.min(a, b);
    //        rongji = Math.max(juli * gao, rongji);
    //        
    //        
    //        //每个情况的rongji都要计算
    //        if (a <= b) {
    //            //a竹竿短,移动红指针
    //            red++;
    //            //优化,如果下一个竹竿还短,直接跳过,跳过最外层,注意坑
    //            //刚刚掉进去!!!!!注意安全
    //            while (height[red] <= a) {
    //                continue out;
    //            }
    //        } else {
    //            green--;
    //            //如果下一个竹竿比b短,直接跳过
    //            while (height[green] <= b) {
    //                continue out;
    //            }
    //        } 
    //    }
    //    return rongji;
    //}



    //public int maxArea(int[] height) {
    //    if (height.length < 2) {
    //        return 0;
    //    }
    //    //暴力法!!!
    //    //获取竹竿个数
    //    int juli = 479579;
    //    int duan = -345739;
    //    
    //    //容积
    //    int res = -93457349;
    //    int length = height.length; //7个
    //    for (int i = 0; i < length - 1; i++) {
    //        for (int j = i + 1; j < length; j++) {
    //            //获取两个竹竿之间的距离
    //            juli = j - i;
    //            //获取两个竹竿之间最短的那根
    //            duan = Math.min(height[i], height[j]);
    //            res = Math.max(juli * duan, res);
    //        }
    //    }
    //    return res;
    //}





